import java.util.LinkedList;
import java.util.List;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}
//class Solution {
//    public List<List<Integer>> pathSum(TreeNode root
//            , int targetsum) {
//        List<List<Integer>> res = new ArrayList<>();
//        if (root == null) return res; // 非空判断
//        List<Integer> path = new LinkedList<>();
//        preorderdfs(root, targetsum, res, path);
//        return res;
//    }
//    public void preorderdfs(TreeNode root,
//                            int targetsum,
//        List<List<Integer>> res, List<Integer> path) {
//        path.add(root.val);//利用一维数组来存储值
//        // 遇到了叶子节点
//        if (root.left == null && root.right == null) {
//            // 找到了和为 targetsum 的路径
//            if (targetsum - root.val == 0) {
//                res.add(new ArrayList<>(path));
//            }
//            return; // 如果和不为 targetsum，返回
//        }
//
//        if (root.left != null) {
//            preorderdfs(root.left,
//             targetsum - root.val, res, path);
//            path.remove(path.size() - 1); // 回溯
//        }
//        if (root.right != null) {
//            preorderdfs(root.right,
//            targetsum - root.val, res, path);
//            path.remove(path.size() - 1); // 回溯
//        }
//    }
//}

// class Solution {
//     public List<List<Integer>> pathSum(TreeNode root, int targetsum) {
//         List<List<Integer>> res = new ArrayList<>();
//         if (root == null) return res; // 非空判断
//         List<Integer> path = new LinkedList<>();
//         preorderdfs(root, targetsum, res, path);
//         return res;
//     }
//     public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
//         path.add(root.val);//利用一维数组来存储值
//         // 遇到了叶子节点
//         if (root.left == null && root.right == null) {
//             // 找到了和为 targetsum 的路径
//             if (targetsum - root.val == 0) {
//                 res.add(new ArrayList<>(path));
//             }
//             return; // 如果和不为 targetsum，返回
//         }

//         if (root.left != null) {
//             preorderdfs(root.left, targetsum - root.val, res, path);
//             path.remove(path.size() - 1); // 回溯
//         }
//         if (root.right != null) {
//             preorderdfs(root.right, targetsum - root.val, res, path);
//             path.remove(path.size() - 1); // 回溯
//         }
//     }
// }

 // 解法2
 class Solution {
     List<List<Integer>> result;
     LinkedList<Integer> path;
     public List<List<Integer>> pathSum (TreeNode root, int targetSum) {
         result = new LinkedList<>();
         path = new LinkedList<>();
         travesal(root, targetSum);
         return result;
     }
     private void travesal(TreeNode root,  int count) {
         if (root == null) return;
         path.offer(root.val);
         count -= root.val;
         if (root.left == null && root.right == null && count == 0) {
             result.add(new LinkedList<>(path));
         }
         travesal(root.left, count);
         travesal(root.right, count);
         path.removeLast(); // 回溯
     }
 }


public class TestDemo {

    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(11);
        TreeNode node5 = new TreeNode(13);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(2);
        TreeNode node9 = new TreeNode(5);
        TreeNode node10 = new TreeNode(1);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node4.left = node7;
        node4.right = node8;
        node3.left = node5;
        node3.right = node6;
        node6.left = node9;
        node6.right = node10;
        solution.pathSum(node1, 22);
    }
}